package com.xc.ksxt;

import java.util.*;

public class StringSimilarity {

    /**
     * 使用Levenshtein距离计算相似度（编辑距离）
     * @param s1 第一个字符串
     * @param s2 第二个字符串
     * @return 相似度百分比（0-100）
     */
    public static double levenshteinSimilarity(String s1, String s2) {
        if (s1 == null || s2 == null) return 0.0;

        int[] prevRow = new int[s2.length() + 1];
        for (int j = 0; j <= s2.length(); j++) {
            prevRow[j] = j;
        }

        for (int i = 1; i <= s1.length(); i++) {
            int[] currRow = new int[s2.length() + 1];
            currRow[0] = i;

            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= s2.length(); j++) {
                char c2 = s2.charAt(j - 1);
                int insertions = prevRow[j] + 1;
                int deletions = currRow[j - 1] + 1;
                int substitutions = prevRow[j - 1] + (c1 != c2 ? 1 : 0);
                currRow[j] = Math.min(Math.min(insertions, deletions), substitutions);
            }
            prevRow = currRow;
        }

        int distance = prevRow[s2.length()];
        int maxLength = Math.max(s1.length(), s2.length());
        return (maxLength - distance) / (double) maxLength * 100;
    }

    /**
     * 使用Jaro-Winkler距离计算相似度
     * @param s1 第一个字符串
     * @param s2 第二个字符串
     * @return 相似度百分比（0-100）
     */
    public static double jaroWinklerSimilarity(String s1, String s2) {
        if (s1 == null || s2 == null) return 0.0;
        if (s1.equals(s2)) return 100.0;

        int len1 = s1.length();
        int len2 = s2.length();
        int maxLen = Math.max(len1, len2);
        int match = 0;
        int k = 0; // 前缀匹配计数器

        // 计算匹配字符
        while (k < len1 && k < len2 && s1.charAt(k) == s2.charAt(k)) {
            match++;
            k++;
        }

        // 如果前缀匹配超过一定长度，直接返回较高相似度
        if (match > 0) {
            double score = (match / (double) maxLen) * 100;
            return Math.min(score, 100.0);
        }

        // 使用滑动窗口查找其他匹配字符
        int window = Math.max(1, (int) (maxLen / 100));
        boolean[] s1Flags = new boolean[len1];
        boolean[] s2Flags = new boolean[len2];

        for (int i = 0; i < len1; i++) {
            if (!s1Flags[i]) {
                int j = Math.max(0, i - window);
                while (j < len2 && (s2Flags[j] || Math.abs(i - j) > window)) {
                    j++;
                }
                if (j < len2 && !s2Flags[j] && s1.charAt(i) == s2.charAt(j)) {
                    match++;
                    s1Flags[i] = true;
                    s2Flags[j] = true;
                }
            }
        }

        return (match / (double) maxLen) * 100;
    }

    /**
     * 使用TF-IDF计算余弦相似度
     * @param s1 第一个字符串
     * @param s2 第二个字符串
     * @return 相似度百分比（0-100）
     */
    public static double cosineSimilarity(String s1, String s2) {
        if (s1 == null || s2 == null) return 0.0;

        // 简单分词（按空格分割，实际应用需要更复杂的分词）
        Map<String, Integer> tf1 = getTermFrequency(s1);
        Map<String, Integer> tf2 = getTermFrequency(s2);

        // 计算TF-IDF
        Map<String, Double> tfidf1 = new HashMap<>();
        Map<String, Double> tfidf2 = new HashMap<>();
        double maxIdf = 0.0;

        for (String term : tf1.keySet()) {
            double idf = Math.log((double) (tf1.size() + 1) / tf1.get(term));
            tfidf1.put(term, tf1.get(term) * idf);
            maxIdf = Math.max(maxIdf, idf);
        }

        for (String term : tf2.keySet()) {
            double idf = Math.log((double) (tf2.size() + 1) / tf2.get(term));
            tfidf2.put(term, tf2.get(term) * idf);
            maxIdf = Math.max(maxIdf, idf);
        }

        // 计算点积和模长
        double dotProduct = 0.0;
        double norm1 = 0.0;
        double norm2 = 0.0;

        for (String term : tfidf1.keySet()) {
            if (tfidf2.containsKey(term)) {
                dotProduct += tfidf1.get(term) * tfidf2.get(term);
            }
            norm1 += Math.pow(tfidf1.get(term), 2);
        }

        for (String term : tfidf2.keySet()) {
            if (!tfidf1.containsKey(term)) {
                norm2 += Math.pow(tfidf2.get(term), 2);
            }
        }

        norm2 += norm1; // 因为已经包含在上面的循环中？

        double cosine = dotProduct / (Math.sqrt(norm1) * Math.sqrt(norm2));
        return Math.min(Math.max(cosine, 0.0), 1.0) * 100;
    }

    private static Map<String, Integer> getTermFrequency(String text) {
        Map<String, Integer> freq = new HashMap<>();
        if (text == null || text.isEmpty()) return freq;

        String[] tokens = text.split("\\s+");
        for (String token : tokens) {
            if (token.isEmpty()) continue;
            freq.put(token, freq.getOrDefault(token, 0) + 1);
        }
        return freq;
    }

    public static void main(String[] args) {
        System.out.println(Math.abs(-10));
        String s1 = "与四分位数间距相比，极差<br/>";
        String s2 = "与四分位数间距相比，极差<br/>";

        System.out.println("Levenshtein Similarity: " + levenshteinSimilarity(s1, s2) + "%");
        System.out.println("Jaro-Winkler Similarity: " + jaroWinklerSimilarity(s1, s2) + "%");
        System.out.println("Cosine Similarity: " + cosineSimilarity(s1, s2) + "%\n");

        s1 = "hello world";
        s2 = "hallo world";

        System.out.println("Levenshtein Similarity: " + levenshteinSimilarity(s1, s2) + "%");
        System.out.println("Jaro-Winkler Similarity: " + jaroWinklerSimilarity(s1, s2) + "%");
        System.out.println("Cosine Similarity: " + cosineSimilarity(s1, s2) + "%\n");

        s1 = "apple";
        s2 = "apples";

        System.out.println("Levenshtein Similarity: " + levenshteinSimilarity(s1, s2) + "%");
        System.out.println("Jaro-Winkler Similarity: " + jaroWinklerSimilarity(s1, s2) + "%");
        System.out.println("Cosine Similarity: " + cosineSimilarity(s1, s2) + "%");
    }
}